//请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。 
//
// 
// 数字 1-9 在每一行只能出现一次。 
// 数字 1-9 在每一列只能出现一次。 
// 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图） 
// 
//
// 
//
// 注意： 
//
// 
// 一个有效的数独（部分已被填充）不一定是可解的。 
// 只需要根据以上规则，验证已经填入的数字是否有效即可。 
// 空白格用 '.' 表示。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：board = 
//[["5","3",".",".","7",".",".",".","."]
//,["6",".",".","1","9","5",".",".","."]
//,[".","9","8",".",".",".",".","6","."]
//,["8",".",".",".","6",".",".",".","3"]
//,["4",".",".","8",".","3",".",".","1"]
//,["7",".",".",".","2",".",".",".","6"]
//,[".","6",".",".",".",".","2","8","."]
//,[".",".",".","4","1","9",".",".","5"]
//,[".",".",".",".","8",".",".","7","9"]]
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：board = 
//[["8","3",".",".","7",".",".",".","."]
//,["6",".",".","1","9","5",".",".","."]
//,[".","9","8",".",".",".",".","6","."]
//,["8",".",".",".","6",".",".",".","3"]
//,["4",".",".","8",".","3",".",".","1"]
//,["7",".",".",".","2",".",".",".","6"]
//,[".","6",".",".",".",".","2","8","."]
//,[".",".",".","4","1","9",".",".","5"]
//,[".",".",".",".","8",".",".","7","9"]]
//输出：false
//解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无
//效的。 
//
// 
//
// 提示： 
//
// 
// board.length == 9 
// board[i].length == 9 
// board[i][j] 是一位数字（1-9）或者 '.' 
// 
// Related Topics 数组 哈希表 矩阵 
// 👍 891 👎 0


package com.cjl.leetcode.editor.cn;

import java.util.*;

/**
 * [P36]_有效的数独
 *
 * @author cjl
 * @date 2022-06-04 20:27:43
 */
public class P36_ValidSudoku {
    public static void main(String[] args) {
        //测试代码
        Solution solution = new P36_ValidSudoku().new Solution();
        int b[][] = {{1,2},{},{3,4,5}};
        char[][] ch= {{'5','3','.','.','7','.','.','.','.'}
                ,{'6','.','.','1','9','5','.','.','.'}
                ,{'.','9','8','.','.','.','.','6','.'}
                ,{'8','.','.','.','6','.','.','.','3'}
                ,{'4','.','.','8','.','3','.','.','1'}
                ,{'7','.','.','.','2','.','.','.','6'}
                ,{'.','6','.','.','.','.','2','8','.'}
                ,{'.','.','.','4','1','9','.','.','5'}
                ,{'.','.','.','.','8','.','.','7','9'}};
        System.out.println("args = " + solution.isValidSudoku(ch));
    }

    //力扣代码
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 解题思路：每个位置对应不同的三个【0-9】数列，遍历时，发现有重复则时无效，遍历完没有重复则是有效
         * 第i行队列标识 ，hArray[i]
         * 第j列队列标识，lArray[j + 9]
         * 第i行j列对应队列标识，9array[i/3+ j/3 * 3 + 18]
         *
         * @param board
         * @return
         */
        public boolean isValidSudoku(char[][] board) {
            Set<Character>[] array = new HashSet[27];
            for (int i = 0; i < array.length; i++) {
                Set<Character> map = new HashSet<>();
                array[i] = map;
            }
            for (int i = 0; i < board.length; i++) {
                for (int j = 0; j < board[i].length; j++) {
                    char key = board[i][j];
                    if (key != '.') {
                        Set<Character> hset = array[i];
                        Set<Character> lset = array[j + 9];
                        Set<Character> hlset = array[i / 3 + j / 3 * 3 + 18];
                        if (hset.contains(key) || lset.contains(key) || hlset.contains(key)) {
                            return false;
                        } else {
                            hset.add(key);
                            lset.add(key);
                            hlset.add(key);
                        }
                    }
                }
            }
            return true;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}